package alo.p6.work4;

import alo.p6.BinarySearchTreeNode;

/**
 * @ClassName FloorCeilingInBST
 * @Description 求某值在二叉搜索树中的上下限结点
 * @Author Fanxc
 * @DATE 2021/2/22 15:45
 * @Version 1.0
 */
public class FloorCeilingInBST {
    //上限
    BinarySearchTreeNode floorInBST(BinarySearchTreeNode root,int data){
        BinarySearchTreeNode prev=null;
        return floorINBSTUtil(root,prev,data);
    }

    BinarySearchTreeNode floorINBSTUtil(BinarySearchTreeNode root,BinarySearchTreeNode prev,int data) {
        if (root==null){
            return null;
        }
        if (floorINBSTUtil(root.getLeft(),prev,data)!=null){
            return floorINBSTUtil(root.getLeft(),prev,data);
        }
        if (root.getData()==data){
            return root;
        }
        if (root.getData()>data){
            return prev;
        }
        prev=root;
        return floorINBSTUtil(root.getRight(),prev,data);
    }


    //下限
    BinarySearchTreeNode ceilingInBST(BinarySearchTreeNode root,int data){
        BinarySearchTreeNode prev=null;
        return ceilingINBSTUtil(root,prev,data);
    }

    BinarySearchTreeNode ceilingINBSTUtil(BinarySearchTreeNode root,BinarySearchTreeNode prev,int data) {
        if (root==null){
            return null;
        }
        if (ceilingINBSTUtil(root.getRight(),prev,data)!=null){
            return ceilingINBSTUtil(root.getRight(),prev,data);
        }
        if (root.getData()==data){
            return root;
        }
        if (root.getData()<data){
            return prev;
        }
        prev=root;
        return ceilingINBSTUtil(root.getLeft(),prev,data);
    }
}
